Przechadzka Bajtusia

Limit pamięci: 128 MB

Bajtuś jest jednym z najmłodszych mieszkańców Bajtogrodu. Dopiero niedawno nauczył się pisać i czytać. Jest jednak na tyle duży, że sam już chodzi do szkoły. Codziennie rano wychodzi z domu, a następnie wstępuje po kolei do wszystkich swoich kolegów; dopiero po dołączeniu się ostatniego kolegi cała grupa idzie na lekcje.

Pewnego dnia nauczyciel Bajtusia poprosił go o sporządzenie listy ulic, którymi Bajtuś przechodzi po drodze z domu do szkoły, i odczytanie tej listy na następnych zajęciach. Szybko jednak okazało się, że taka lista mogłaby pochłonąć ogromne ilości papieru. Ustalono więc, że Bajtuś zapisze jedynie pierwszą literę z nazwy każdej ulicy, po której przejdzie. Każda ulica w Bajtogrodzie jest jednokierunkowa i łączy dwa różne skrzyżowania.

Bajtuś podczas odczytywania opisu trasy robi przerwy jedynie w miejscach, w których wstępował do kolegów. Możemy więc traktować opis każdego fragmentu jego drogi z domu do szkoły jako jedno słowo. Chłopiec wciąż ma problemy z prawidłowym czytaniem, tj. czytaniem od lewej strony do prawej, i zamiast tego zdarza mu się czytać od strony prawej do lewej. Czasem przeczyta wyraz mleko jako mleko, a czasem jako okelm. Rodzice Bajtusia wiedzą o tych problemach syna, więc postanowili mu pomóc i znaleźć taką trasę, by opis każdego fragmentu, niezależnie od tego, z której strony czytany, brzmiał tak samo. Jednocześnie chcieliby, żeby długość każdego kawałka tej trasy była jak najmniejsza. Zwrócili się do Ciebie z prośbą o pomoc.

Napisz program, który:

• wczyta ze standardowego wejścia opis miasta,
• wyznaczy taką trasę z domu do szkoły, w której każdy fragment jest możliwie najkrótszy, a jego opis, niezależnie od kierunku czytania, brzmi dokładnie tak samo,
• wypisze wyznaczone opisy fragmentów drogi na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite i oddzielone pojedynczym odstępem (, ). Oznaczają one odpowiednio liczbę skrzyżowań w Bajtogrodzie oraz liczbę łączących je ulic. W kolejnych wierszach znajdują się opisy ulic. W wierszu -szym znajdują się trzy wartości , , (, , ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio początek ulicy, koniec ulicy oraz pierwszą literę jej nazwy w postaci małej litery alfabetu angielskiego. Między dowolnymi dwoma skrzyżowaniami istnieje maksymalnie jedna ulica w danym kierunku. Kolejny wiersz zawiera jedną liczbę całkowitą (), oznaczającą liczbę skrzyżowań, pomiędzy którymi idzie Bajtuś w drodze do szkoły. Następny wiersz zawiera liczb całkowitych (), pooddzielanych pojedynczymi odstępami. Oznaczają one, że Bajtuś mieszka przy skrzyżowaniu numer , szkoła znajduje się przy skrzyżowaniu , zaś po drodze Bajtuś idzie kolejno po kolegów mieszkających przy skrzyżowaniach . Każde dwa następujące po sobie numery skrzyżowań na liście są różne. Może się jednak zdarzyć, że pewne numery skrzyżowań na liście będą takie same. Ponadto, jeśli pomiędzy dwoma kolejnymi skrzyżowaniami nie da się przejść, stosując się do ograniczeń podanych w zadaniu, to Bajtuś idzie na przełaj i niczego nie zapisuje na kartce.

Wyjście

Wyjście powinno składać się z wierszy. W -tym wierszu powinna znajdować się liczba oraz ciąg znaków , oddzielone pojedynczym odstępem. Liczba oznacza długość najkrótszej drogi, spełniającej wymogi zadania, łączącej skrzyżowania oraz , zaś to ciąg pierwszych liter nazw ulic na tej drodze. W przypadku gdy pomiędzy danymi dwoma skrzyżowaniami nie istnieje trasa spełniająca warunki zadania, należy wypisać . Jeśli zaś istnieje kilka możliwych ciągów znaków zgodnych z warunkami zadania, należy wypisać dowolny z nich.

Przykład

Dla danych wejściowych:

6 7
1 2 a
1 3 x
1 4 b
2 6 l
3 5 y
4 5 z
6 5 a
3
1 5 3

poprawną odpowiedzią jest:

3 ala
-1

Autor zadania: Mirosław Michalski.